package fun.coding.leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Set;

public class LeetCodeImpl implements LeetCode {
	
    /*http://leetcode.com/onlinejudge#question_29
     * well, of course there will be negative...,
     * well, of course you need to use big so that it is lgN
     * well, of course there will be some overflow 2^31 -1, which makes it quite hard
     * http://discuss.leetcode.com/questions/209/divide-two-integers
     * this must be ACM guy's clean solution.  */
    public int divide(int dividend, int divisor) {
        if (divisor == 0)
            return 0;
        
        int signA = dividend >= 0 ? 1 : -1;
        int signB = divisor > 0 ? 1 : -1;
        int sign = signA * signB;
//        System.out.println("sign is " + sign);
        
        // if it is Integer.MIN, Math.abs will return a negative same value.
        // Make it a long type will solve it. 
        long d = Math.abs((long)dividend);
        long r = Math.abs((long)divisor);
    
//        System.out.println("dividend is " + dividend + "divisor is " + divisor);
        int res = 0;
        
        while (d >= r) {
            int count = 0;
            long total = r;
            
            while (total < (Integer.MAX_VALUE / 2) && (total << 1) < d) {
                count++;
//                System.out.println("count is " + count);
                total = total << 1;
//                System.out.println("total is " + total);
                if (total >= (Integer.MAX_VALUE / 2)) {
                    break;
                }
            }
            
            d -= (int)Math.pow(2, count) * r;
            res += (int)Math.pow(2, count);
//            System.out.println("res is " + res);
        }
        return res * sign;
    }


    /* http://leetcode.com/onlinejudge#question_23
     */
    @Override
    public ListNode mergeKLists(ArrayList<ListNode> lists) {
        if (lists == null || lists.isEmpty()) {
            return null;
        }
        
        PriorityQueue<ListNode> heap = new PriorityQueue<ListNode>(lists.size(), new MyComparator());
        
        for (ListNode node : lists) {
            if (node != null) {
                heap.add(node);
            }
        }
        
        ListNode head = new ListNode(0);
        ListNode res = null; 
    
        // Just keep track of head.
        if (!heap.isEmpty()) {
            res = heap.peek();
        }
        
        while (!heap.isEmpty()) {
            ListNode min = heap.poll();
            head.next = min;
            head = head.next;
            if (min.next != null) {
                heap.add(min.next);
            }
        }
        
        return res;
    }
    
    private class MyComparator implements Comparator<ListNode> {

        @Override
        public int compare(ListNode o1, ListNode o2) {
            return o1.val - o2.val;
        }
    }
	
	/* http://leetcode.com/onlinejudge#question_91
	 * 123 could be decoded as (A,B,C), (A,W) (I,C) return 3
	 * TODO: not right. 
	 * http://www.mitbbs.com/article_t/JobHunting/32190699.html
	 * */
    @Override
    public int numDecodings(String s) {
        if (s == null || s.isEmpty())
            return 0;
      
        if (s.length() == 1) {
            return s.charAt(0) == '0' ? 0 : 1;
        }
        
        int fn = 0;
        int fn_2 = (s.charAt(0) == '0' ? 0 : 1);
        int fn_1 = (s.charAt(0) == '1' || (s.charAt(0) == '2' && s.charAt(1) <= '6')) ? 1 : 0 + fn_2;
        if (s.length() == 2) {
            return fn_2 + (s.charAt(1) == '0' ? 0 : fn_1);
        }        
        
        for (int i = 2; i < s.length(); ++i) {
            if (s.charAt(i) != 0) {
                fn += fn_1;
            }
            if (s.charAt(i - 1) == '1' || (s.charAt(i-1) == '2' && s.charAt(i) <= '6')) {
                fn += fn_2;
            }
            fn_2 = fn_1;
            fn_1 = fn;
        }
        
        return fn;
    }
    
    /*http://leetcode.com/onlinejudge#question_70
     * Given n stairs, how many distinct ways to reach the stairs
     * C(N^2)*/
    @Override
    public int climbStairs(int n) {
        if (n <= 0) return 0;
        if (n == 1) return 1;
        if (n == 2) return 2;
        int fn = 0;
        int fn_1 = 2;
        int fn_2 = 1;
        
        for (int i = 3; i <= n; ++i) {
            fn = fn_1 + fn_2;
            // Note the order here
            fn_2 = fn_1;
            fn_1 = fn;
        }
        return fn;
    }

    public ArrayList<ArrayList<Integer>> permuteRecursive(int[] num) {
    	ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
    	if (num == null || num.length == 0) {
    		return res;
    	}
    	ArrayList<Integer> cur = new ArrayList<Integer>();
    	int[] visited = new int[num.length];
    	permuteRecursiveHelper(res, cur, num, visited);
    	
    	return res;
    }

    /* Solving the permutation recursively. 
     *                    {}
     *               1     2        3  
     *            12, 13  21, 23,   31, 32
     *          123, 132, 213, 231, 312, 321
     * */    
    private void permuteRecursiveHelper(ArrayList<ArrayList<Integer>> res, ArrayList<Integer> cur, int[] num, int[] visited) {
    	if (cur.size() == num.length) {
    		ArrayList<Integer> tmp = new ArrayList<Integer>();
    		for (int i : cur) {
    			tmp.add(i);
    		}
    		res.add(tmp);
    		return;
    	}
    	
    	for (int i = 0; i < num.length; ++i) {
    		if (visited[i] == 1) continue;
    		
    		cur.add(num[i]);
    		visited[i] = 1;
    		permuteRecursiveHelper(res, cur, num, visited);
    		cur.remove(cur.size() - 1);
    		visited[i] = 0;
    	}
    }
    
    /* http://leetcode.com/onlinejudge#question_46
     * Permutate the array, 
     * [1,2,3] have 6 different permutations. 
     * It is N!
     * */
    @Override
    public ArrayList<ArrayList<Integer>> permute(int[] num) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        if (num == null || num.length == 0) return res;
        
        for (int i = 0; i < num.length; ++i)
            res = permuteHelper(res, num[i]);
        
        return res;
    }
	
    private ArrayList<ArrayList<Integer>> permuteHelper(ArrayList<ArrayList<Integer>> numArray, int num) {
        if (numArray.isEmpty()) {
            ArrayList<Integer> res = new ArrayList<Integer>();
            res.add(num);
            numArray.add(res);
            ArrayList<ArrayList<Integer>> r = new ArrayList<ArrayList<Integer>>();
            r.add(res);
            return r;
        }
        ArrayList<ArrayList<Integer>> r = new ArrayList<ArrayList<Integer>>();
        
        for (ArrayList<Integer> it : numArray) {
            r.addAll(insert(it, num));
        }
        return r;
    }
    
    private ArrayList<ArrayList<Integer>> insert(ArrayList<Integer> array, int num) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        for (int i = 0; i <= array.size(); ++i) {
            ArrayList<Integer> temp = new ArrayList<Integer>();
            for (int j = 0; j < array.size(); ++j) {
                temp.add(array.get(j));
            }
            temp.add(i, num);
            res.add(temp);
        }
        
        return res;
    }

    @Override
    public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        res = permute(num);
        HashSet<ArrayList<Integer>> r = new HashSet<ArrayList<Integer>>();
        for (ArrayList<Integer> it : res) {
            r.add(it);
        }
        
        return new ArrayList<ArrayList<Integer>>(r);
    }
    
    /* subset, e.g., [1,2] has 4 subsets.
     * */
    public ArrayList<ArrayList<Integer>> subsets1(int[] S) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        
        if (S == null || S.length == 0) {
            return res;
        }
        
        Arrays.sort(S);
        
        for (int i = 0; i < Math.pow(2, S.length); ++i) {
            ArrayList<Integer> a = new ArrayList<Integer>();
            int index = 0;
            int n = i;
            while (n > 0) {
                if ((n & 1) == 1) {
                    a.add(S[index]);
                }
                index++;
                n = n >> 1;
            }
            res.add(a);
        }
        
        return res;
    }
    
    @Override
    public boolean isValidSudoku(char[][] board) {
        if (board == null) return false;
        int[] mark = new int[9];
        resetMarker(mark);
        
        for (int i = 0; i < 9; ++i) {
            // check each row
            for (int j = 0; j < 9; ++j) {
                if (board[i][j] == '.')
                    continue;
                if (mark[board[i][j] - '1'] == 1) {
                    return false;
                } else {
                    mark[board[i][j] - '1'] = 1;
                }
            }
            resetMarker(mark);
        }
        
        // could save the column checking by using another marker. 
        for (int i = 0; i < 9; ++i) {
            // check each col
            for (int j = 0; j < 9; ++j) {
                if (board[j][i] == '.')
                    continue;
                if (mark[board[j][i] - '1'] == 1) {
                    return false;
                } else {
                    mark[board[j][i] - '1'] = 1;
                }
            }
            resetMarker(mark);
        } 
        
        for (int i = 0; i < 9; i+=3) {
            for (int j = 0; j < 9; j+=3) {
                for (int k = 0; k < 3; ++k) {
                    for(int t = 0; t < 3; ++t) {
                        if (board[i+k][j+t] == '.')
                            continue;
                        if (mark[board[i+k][j+t] - '1'] == 1) {
                            return false;
                        }
                        else {
                            mark[board[i+k][j+t] - '1'] = 1;
                        }
                    }
                }
                resetMarker(mark);
            }
        }
        
        return true;
    }
    
    private void resetMarker(int[] mark) {
        for(int i = 0; i < 9; ++i) {
            mark[i] = 0;
        }
    }
    
    /*Recursion will have O(N) worst case but would terminate early, it is better than using a combination of inorder and pre/post order traversal. */
    @Override
    public boolean isSameTree(TreeNode p, TreeNode q) {
    	if (p == null && q == null) {
    		return true;
    	} 
    	
    	if ((p == null && q != null) || (p != null && q == null)) {
    		return false;
    	}
    	
    	if (p != null && q != null) {
    		if (p.val != q.val) {
    			return false;
    		} else {
    			return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    		}
    	}
    	return false;
    }
    
    @Override
    public ArrayList<ArrayList<Integer>> subsetsWithDup(int[] num) {
    	ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
    	if (num == null)
    		return res;
    	
    	Arrays.sort(num);
    	ArrayList<Integer> cur = new ArrayList<Integer>();
    	subsetWithDupHelper(res, cur, num, 0);
    	res.add(cur);
    	return res;
    }
    
    private void subsetWithDupHelper(ArrayList<ArrayList<Integer>> res, ArrayList<Integer> cur, int[] s, int index) {
    	for (int i = index; i < s.length; ++i) {
    		// This is so nice, note we would still add the first duplicate if it is its first apperance. 
    		if (i != index && s[i] == s[i-1]) continue;
    		
    		cur.add(s[i]);
    		
    		ArrayList<Integer> tmp = new ArrayList<Integer>();
    		for (int it : cur) {
    			tmp.add(it);
    		}
    		
    		res.add(tmp);
    		
    		subsetWithDupHelper(res, cur, s, i + 1);
    		
    		cur.remove(cur.size() - 1);
    		
    	}
    }
    
    /* Recursively solving the subset, now subsets and permutations are so easy for me :) 
     * 
     *                  {}
     *           1      2       3
     *        12,13     23       
     *       123,  
     * */
    public ArrayList<ArrayList<Integer>> subsetsRec(int[] S) {
    	ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
    	if (S == null)
    		return res;
    	
    	Arrays.sort(S);
    	ArrayList<Integer> cur = new ArrayList<Integer>();
    	subsetRecHelper(res, cur, S, 0);
    	res.add(cur);
    	return res;
    }
    
    private void subsetRecHelper(ArrayList<ArrayList<Integer>> res, ArrayList<Integer> cur, int[] s, int index) {
    	for (int i = index; i < s.length; ++i) {
    		cur.add(s[i]);
    		
    		ArrayList<Integer> tmp = new ArrayList<Integer>();
    		for (int it : cur) {
    			tmp.add(it);
    		}
    		res.add(tmp);
    		
    		subsetRecHelper(res, cur, s, i + 1);
    		cur.remove(cur.size() - 1);
    	}
    }
    
    /*totall understand it, it is just using that tree to parse it. 
     * e.g., 1, 2, 3, starting from empty
     *                {}
     *          1      2         3
     *         12,13   23
     * 	this is C3-2
     * 
     * */
    @Override
    public ArrayList<ArrayList<Integer>> combine(int n, int k) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
    	if (n < k || n <= 0 || k < 0) {
    		return res;
    	}
    	
    	ArrayList<Integer> cur = new ArrayList<Integer>();
    	combineHelper(res, cur, 1, k, n);
    	return res;
    }
    
    private void combineHelper(ArrayList<ArrayList<Integer>> res, ArrayList<Integer> cur, int index, int k, int n) {
    	if (cur.size() == k) {
    		ArrayList<Integer> tmp = new ArrayList<Integer>();
    		for(int i : cur) {
    			tmp.add(i);
    		}
            res.add(tmp);
    		return;
    	}
    	
    	for (int i = index; i <= n; ++i) {
    		cur.add(i);
    		combineHelper(res, cur, i + 1, k, n);
    		cur.remove(cur.size() - 1);
    	}
    }
    /* http://leetcode.com/onlinejudge#question_101
     * */
    @Override
    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;
        
        return isSymmetricHelper(root.left, root.right);
    }
    
    private boolean isSymmetricHelper(TreeNode t1, TreeNode t2) {
        if (t1 == null && t2 == null) return true;
        
        if ((t1 == null && t2 != null) || (t1 != null && t2 == null)) return false;
        
        if (t1.val != t2.val) return false;
        
        return isSymmetricHelper(t1.left, t2.right) && isSymmetricHelper(t1.right, t2.left);
    }
    
    /*http://leetcode.com/onlinejudge#question_102
     * level order traverse a tree.
     * */
    @Override
    public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
        Queue<TreeNode> cur = new LinkedList<TreeNode>();
        
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        
        if (root == null) return res;
        
        cur.add(root);
        
        while (!cur.isEmpty()) {
            ArrayList<Integer> level = new ArrayList<Integer>();
            Queue<TreeNode> next = new LinkedList<TreeNode>();
            for (TreeNode t : cur) {
                level.add(t.val);
                if (t.left != null) {
                    next.add(t.left);
                }
                if (t.right != null) {
                    next.add(t.right);
                }
            }
            res.add(level);
            cur = next;
        }
        
        return res;
    }
    
    /* http://leetcode.com/onlinejudge#question_103
     * similar to level order except it is zig zag order.
     * This is really a naive solution just by reversing the queue order when it is from right to left.  
     * */
    @Override
    public ArrayList<ArrayList<Integer>> zigzagLevelOrder(TreeNode root) {
        Queue<TreeNode> cur = new LinkedList<TreeNode>();
        
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        
        if (root == null) return res;
        
        cur.add(root);
        
        boolean isFromLeftToRight = true;
        while (!cur.isEmpty()) {
            ArrayList<Integer> level = new ArrayList<Integer>();
            Queue<TreeNode> next = new LinkedList<TreeNode>();
            for (TreeNode t : cur) {
                level.add(t.val);
                if (t.left != null) {
                    next.add(t.left);
                }
                if (t.right != null) {
                    next.add(t.right);
                }
            }
            
            if (!isFromLeftToRight) {
               // here I could use Collections.reverse(level)
               reverseArrayList(level);
            }
            res.add(level);

            isFromLeftToRight = !isFromLeftToRight;
            cur = next;
        }
        
        return res;
    }
    
    private void reverseArrayList(ArrayList<Integer> a) {
        if (a == null) return;
        
        int i = 0;
        int j = a.size() - 1;
        
        while (i < j) {
            int temp = a.get(i);
            a.set(i, a.get(j));
            a.set(j, temp);
            i++;
            j--;
        }
        return;
    }
    
    /* This is a simple version, root-to-leaf path sums to a number. 
     * http://leetcode.com/onlinejudge#question_112
     * */
    @Override
    public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null) return false;
        
        if (root.val == sum && root.left == null && root.right == null) return true;
        
        return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
    }
    
    /* Similar to the original one, but need to return all the solutions. 
     * http://leetcode.com/onlinejudge#question_113
     * */
    @Override
    public ArrayList<ArrayList<Integer>> pathSum(TreeNode root, int sum) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        
        ArrayList<Integer> cur = new ArrayList<Integer>();
        
        pathSumHelper(res, cur, root, sum);
        
        return res;
    }
    // FIXME: probably need to do a deep copy. 
    private void pathSumHelper(ArrayList<ArrayList<Integer>> res, ArrayList<Integer> cur, TreeNode node, int sum) {
        if (node == null) return; 
            
        if (node.val == sum && node.left == null && node.right == null) {
            res.add(cur);
            return;
        }

        cur.add(node.val);
        pathSumHelper(res, cur, node.left, sum - node.val);
        cur.remove(cur.size() - 1);
        pathSumHelper(res, cur, node.right, sum - node.val);
        
    }
    
    /* using the naive solution will exceed time, need to divide it
     *  number of counts = a + n/a, thus a = sqrt(n) */
    @Override
    public double pow(double x, int n) {
    	if (x == 0 && n != 0) return 0;
        
        if (n == 0) return 1;
        
        if (n == 1) return x;
        
        if (n == -1) return 1/x;

        if (x == 1) return 1;
        
        if (x == -1) return (n % 2) == 0 ? 1 : -1;
        
        if (n < 0) {
            x = 1.0 / x;
            n = Math.abs(n);
        }
    	
        double res = x;
        
        long s = Math.round(Math.sqrt(n));
        // first iteration, calculate s
        for (int i = 0; i < s - 1; ++i) {
        	res *= x;
        }
        // 2nd iteration, n/s
        double tmp = res;
        for (int i = 0; i < n/s - 1; ++i) {
        	res *= tmp;
        }
        // 3rd iteration, calucate remainder. 
        for (int i = 0; i < n % s; ++i) {
        	res *= x;
        }
        
    	return res;
    }
    
    public double powNaive(double x, int n) {
        if (x == 0 && n != 0) return 0;
        
        if (n == 0) return 1;
        
        if (n < 0) {
            x = 1.0 / x;
            n = Math.abs(n);
        }
        
        double res = x;
        
        for (int i = 0; i < n - 1; ++i) {
            res *= x;
        }
        return res;
    }
    
    /**
     * http://leetcode.com/onlinejudge#question_111
     * min depth of a binary tree
     */
    public int minDepth(TreeNode root) {
        if (root == null) return 0;
        
        if (root.left == null && root.right == null) {
            return 1;
        } else if (root.left != null && root.right == null) {
            return minDepth(root.left) + 1;
        } else if (root.left == null && root.right != null) {
            return minDepth(root.right) + 1;
        } else {
        
          return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
        }
    }
    
    /**
     * http://oj.leetcode.com/problems/word-break/
     * Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

        For example, given
        s = "leetcode",
        dict = ["leet", "code"].
        
        s = aaaaaaa
        [aaaa, aa]
     */
    @Override
    public boolean wordBreakDFS(String s, Set<String> dict) {
        if (s == null || s.isEmpty() || dict.isEmpty()) {
            return false;
        }
        
        return wordBreakDFSHelper(s, s.length(), dict);
    }
    
    // This is a typical DFS solution. 
    private boolean wordBreakDFSHelper(String s, int index, Set<String> dict) {
        if (dict.contains(s.substring(0, index))) {
            return true;
        }
        
        for (int i = index - 1; i >= 0; i--) {
            if (dict.contains(s.substring(i, index))) {
                // Break early if we found one. 
                if (wordBreakDFSHelper(s, i, dict)) {
                    return true;
                }
            }
        }
        
        return false;
    }
    
    // http://fisherlei.blogspot.com/2013/11/leetcode-word-break-solution.html
    // "dogs", ["dog","s","gs"]
    @Override
    public boolean wordBreak(String s, Set<String> dict) {
        if (s == null || s.isEmpty() || dict.isEmpty()) {
            return false;
        }
        
        boolean[] lookupTable = new boolean[s.length() + 1];
        lookupTable[s.length()] = true;

        for (int i = s.length() - 1; i >= 0; i--) {
            // java string.substring is [)
            for (int j = i; j < s.length(); j++) {
                // The key point here is to build up this lookup table
                // looupTable[i] = if s(i, j+1) is a word & lookupTable[j+1] is true, else false.
                lookupTable[i] = lookupTable[j + 1] && dict.contains(s.substring(i, j + 1));
                if (lookupTable[i]) {
                    break;
                }
            }
            
        }
            
        return lookupTable[0];
    }
    
}
